#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
#include "string.h"


//#define int long long
//using namespace std;
//const int mod = 1e9 + 7;
//const int inf = 1e18;
//const int MAXN = 1e6 + 5;
//int n, a[MAXN];
//vector<int> t[MAXN];
//void dfs(int u, int fa) {
//    a[u] = 1;
//    for (auto v : t[u]) {
//        if (v == fa) continue;
//        dfs(v, u);
//        a[u] += a[v];
//    }
//}
//void solve() {
//    cin >> n;
//    for (int i = 1; i < n; i++) {
//        int u, v; cin >> u >> v;
//        t[u].push_back(v);
//        t[v].push_back(u);
//    }
//    if (n == 1) {
//        cout << "Bob" << endl;
//        return;
//    }
//    dfs(1, 0);
//    int ans = a[t[1][0]];
//    for (int i = 1; i < t[1].size(); i++) {
//        ans ^= a[t[1][i]];
//    }
//    if (ans) cout << "Alice" << endl;
//    else cout << "Bob" << endl;
//    for (int i = 1; i <= n; i++) a[i] = 0, t[i].clear();
//}
//signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    int T; cin >> T;
//    while (T--) solve();
//    return 0;
//}


//vector<vector<int>> children;
//vector<int> sg_values;
//
//void buildTree(int n, const vector<pair<int, int>>& edges) {
//    vector<vector<int>> adj(n + 1);
//    for (const auto& edge : edges) {
//        int u = edge.first, v = edge.second;
//        adj[u].push_back(v);
//        adj[v].push_back(u);
//    }
//
//    vector<bool> visited(n + 1, false);
//    queue<int> q;
//    q.push(1);
//    visited[1] = true;
//
//    children.resize(n + 1);
//
//    while (!q.empty()) {
//        int u = q.front();
//        q.pop();
//        for (int v : adj[u]) {
//            if (!visited[v]) {
//                visited[v] = true;
//                children[u].push_back(v);
//                q.push(v);
//            }
//        }
//    }
//}
//
//void computeSG(int root) {
//    stack<int> s;
//    stack<int> post_order;
//    vector<bool> visited(children.size(), false);
//
//    s.push(root);
//    while (!s.empty()) {
//        int u = s.top();
//        s.pop();
//        post_order.push(u);
//        visited[u] = true;
//        for (int v : children[u]) {
//            if (!visited[v]) {
//                s.push(v);
//            }
//        }
//    }
//
//    while (!post_order.empty()) {
//        int u = post_order.top();
//        post_order.pop();
//        int sg = 0;
//        for (int v : children[u]) {
//            sg ^= (sg_values[v] + 1);
//        }
//        sg_values[u] = sg;
//    }
//}
//
//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//
//    int t;
//    cin >> t;
//    while (t--) {
//        int n;
//        cin >> n;
//        vector<pair<int, int>> edges;
//        for (int i = 0; i < n - 1; ++i) {
//            int u, v;
//            cin >> u >> v;
//            edges.emplace_back(u, v);
//        }
//
//        buildTree(n, edges);
//        if (n == 1) {
//            cout << "Bob\n";
//            children.clear();
//            continue;
//        }
//
//        sg_values.resize(n + 1);
//        computeSG(1);
//        cout << (sg_values[1] != 0 ? "Alice" : "Bob") << '\n';
//
//        children.clear();
//        sg_values.clear();
//    }
//
//    return 0;
//}


//int n;
//vector<int> e[200005];
//int sg[200005];
//
//void dfs(int u, int fa) {
//	sg[u] = 1;
//	for (auto v : e[u]) {
//		if (v != fa) {
//			dfs(v, u);
//			sg[u] += sg[v];
//		}
//	}
//}
//void solve() {
//	cin >> n;
//	for (int i = 1, u, v; i < n; i++) {
//		cin >> u >> v;
//		e[u].push_back(v);
//		e[v].push_back(u);
//	}
//	if (n == 1) {
//		cout << "Bob\n";
//		return;
//	}
//	dfs(1, 0);
//	int ans = e[1][0];
//	for (int i = 1; i < e[1].size(); i++) {
//		ans ^= e[1][i];
//	}
//	if (ans)
//		cout << "Alice\n";
//	else
//		cout << "Bob\n";
//	for (int i = 1; i <= n; i++) sg[i] = 0, e[i].clear();
//	
//}
//
//int t;
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}

//void solve() {
//	int n;
//	cin >> n;
//	for (int i = 1,u,v; i < n; i++) {
//		cin >> u >> v;
//	}
//	if (n == 1)
//		cout << "Bob\n";
//	else
//		cout << "Alice\n";
//}
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}

//const int N = 3e5 + 10;
//ll n, ans, l[N], r[N];
//bool cmp(const ll& x, const ll& y) { return x > y; }
//int main()
//{
//	scanf("%lld", &n);
//	for (int i = 1; i <= n; i++) scanf("%lld %lld", &l[i], &r[i]);
//	sort(l + 1, l + n + 1, cmp), sort(r + 1, r + n + 1);
//	for (int i = 1; i <= n && l[i] > r[i]; i++) ans += (n - 2 * i + 1) * (l[i] - r[i]);
//	printf("%lld", ans);
//	return 0;
//}
//void solve() {
//	cin >> n >> k >> p;
//	k = abs(k);
//	if (k > n * p) {
//		cout << "-1\n";
//		return;
//	}
//	int ans = 0;
//	if (k % p == 0) {
//		ans = k / p;
//	}
//	else {
//		ans = k / p + 1;
//	}
//	cout << ans << '\n';
//}

//int t, a[3],n;
//
//ll qp(int a, int b) {
//	ll res = 1, base = a;
//	while (b) {
//		if (b & 1) res = res * base;
//		base = base * base;
//		b >>= 1;
//	}
//	return res;
//}
//
//void solve() {
//	char c;
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> c;
//		if (c == '-')
//			a[1]++;
//		else
//			a[2]++;
//	}
//	ll ans;
//	if (n < 3)
//		ans = 0;
//	else {
//		int x = a[1] / 2, y = a[1] - x;
//		ans = x * y * a[2];
//	}
//	cout << ans << '\n';
//	a[1] = a[2] = 0;
//}
//
//
//void solve() {
//    int n, x;
//    cin >> n >> x;
//    int base = 0;
//    if (x == 0) {
//        for (int i = 0; i < n; ++i) cout << 0 << ' ';
//        cout << '\n';
//        return;
//    }
//    int lowest_zero = 0;
//    int tmp = x;
//    while ((tmp & 1) == 1) {
//        tmp >>= 1;
//        lowest_zero++;
//    }
//    int max_continuous = (1 << lowest_zero) - 1;
//    int k = min(max_continuous, n - 1);
//    if (k == max_continuous) {
//        for (int i = 0; i < n; ++i) {
//            if (i <= k) cout << i << ' ';
//            else cout << x << ' ';
//        }
//    }
//    else {
//        int remaining = n - (k + 1);
//        for (int i = 0; i <= k; ++i) cout << i << ' ';
//        for (int i = 0; i < remaining; ++i) cout << x << ' ';
//    }
//    cout << '\n';
//}

//
//void solve() {
//	int n, x;
//	cin >> n >> x;
//	if (n == 1) {
//		cout << x << '\n';
//		return;
//	}
//	int base = 1;
//	int tmp = x;
//	while (tmp) {
//		if (tmp & 1) {
//			base *= 2;
//		}
//		else
//			break;
//		tmp >>= 1;
//	}
//	ll high = min(base - 1, n - 1);
//	if (high < base - 1) {
//		tmp = 0;
//		for (int i = 0; i <= n - 2; i++) {
//			cout << i << ' ';
//			tmp |= i;
//		}
//		if ((tmp | (n - 1)) == x)
//			cout << n - 1 << '\n';
//		else
//			cout << x << '\n';
//		return;
//	}
//
//	for (int i = 0; i <= high; i++) {
//		if (i != n - 1)
//			cout << i << ' ';
//		else
//			cout << x << '\n';
//	}
//	for (int i = high + 1; i <= n - 1; i++) {
//		cout << x << ' ';
//	}
//	cout << '\n';
//}

//
//void solve() {
//	int n, x;
//	cin >> n >> x;
//	int high = min(n - 1, x);
//	int tmp = 0;
//	for (int i = 0; i <= high; i++) {
//		if (i == n - 1 && (tmp | i) != x)
//			cout << x << ' ';
//		else
//			cout << i << ' ';
//	}
//}

//void solve() {
//	int n, x;
//	cin >> n >> x;
//	vector<int> ans(n, x);
//	bool ok = 1;
//	int tmp = 0;
//	for (int i = 0; i < n - 1; ++i) {
//		if (((tmp | i) & x) == (tmp | i)) {
//			ans[i] = i;
//			tmp |= i;
//			
//		}
//		else {
//			ok = false;
//			break;
//		}
//	}
//	if (ok && (tmp | (n - 1)) == x)
//		ans[n - 1] = n - 1;
//	for (auto x : ans)cout << x << ' ';
//	cout << '\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}
//
//void solve() {
//	int n;
//	cin >> n;
//	vector<int> a(n+1);
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	int L=1, R=1, best=0;
//	for (int i = 1; i < n; i++) {
//		int cnt_small = 0, cnt_big = 0;
//		for (int j = i + 1; j <= n; j++) {
//			cnt_big += a[i] > a[j];
//			cnt_small += a[i] < a[j];
//			if (best > cnt_small - cnt_big) {
//				L = i, R = j;
//				best = cnt_small - cnt_big;
//			}
//		}
//	}
//	cout << L << ' ' << R << '\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}

//int C[505];
//
//void solve() {
//	int k;
//	cin >> k;
//	if (k == 0) {
//		cout << "0\n";
//		return;
//	}
//	vector<int> ans[500];
//	int n = 0;
//	int x=0,y=0;
//	while (k) {
//		int l = 2, r = 500, m;
//		while (l < r) {
//			m = (l + r + 1) >> 1;
//			if (C[m] <= k)
//				l = m;
//			else
//				r = m - 1;
//		}
//		for (int i = 0; i < l; x++,i++) {
//			ans[y].push_back(x);
//		}
//		k -= C[l];
//		n += l;
//		y++;
//	}
//	cout << n<<'\n';
//	for (int i = 0; i < y; i++) {
//		for (auto x : ans[i])
//			cout << x << ' ' << i << '\n';
//	}
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	C[2] = 1;
//	for (int i = 3; i <= 502; i++) {
//		C[i] = C[i - 1] + i - 1;
//	}
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}

//void solve() {
//	int n, k;
//	cin >> n >> k;
//	if (n == 1) {
//		cout << k << '\n';
//		return;
//	}
//	vector<int> ans(n);
//	for (int i = 2; i <= n; i++) {
//		vector<int> tmp(i);
//		tmp[0] = tmp[i - 1] = k;
//		for (int j = 1; j <= i - 2; j++) {
//			tmp[j] = ans[j - 1] ^ ans[j];
//		}
//		for (int j = 0; j <= i - 1; j++)
//			ans[j] = tmp[j];
//	}
//	for (auto x : ans) {
//		cout << x << ' ';
//	}
//	cout << '\n';
//}


//int C[1000069];
//const int m = 1e6 + 69;
//void build() {
//	C[0] = C[1] = 0;
//	for (int i = 2; i < m; i++) {
//		C[i] = C[i - 1];
//		int x = i;
//		while (x % 2 == 0) {
//			x /= 2, C[i]++;
//		}
//	}
//}
//
//
//void solve() {
//	int n, k;
//	cin >> n >> k;
//	n--;
//	for (int i = 0; i <= n; i++) {
//		cout << k * (C[n] == C[i] + C[n - i])<<' ';
//	}
//	cout << '\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	build();
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	

	return 0;
}